__all__ = ("resolve_deps",)
__license__ = "MIT License <http://www.opensource.org/licenses/mit-license.php>"
__copyright__ = "2005, Tiago Cogumbreiro"
__author__ = "Tiago Cogumbreiro <cogumbreiro@users.sf.net>"

from sets import Set

class InsatisfiedDependencyError(StandardError):
    pass

def split_nodes(nodes):
    unresolved, resolved = [], []
    
    for node in nodes:
        if node.has_deps():
            unresolved.append(node)
        else:
            resolved.append(node)

    return unresolved, resolved


def solve_deps(resolved, unresolved):
    rnodes, unodes = split_nodes(unresolved)
    for res_node in rnodes:
        res_node.unlink_from_nodes(unresolved)
    for node in rnodes:
        resolved.append(node.name)
        
    return resolved, unodes


def solve_circular_deps(resolved, unresolved, nodes):
    node = unresolved[0]
    del unresolved[0]

    # We declare this node as solved and remove the every dependency
    # to it
    node.unlink_from_nodes(unresolved)
    for dep in node.depends:
        # We declare any node linked to this node as solved too
        nodes[dep].unlink_from_nodes(unresolved)
        
    resolved.append(node.name)
    
    rnodes, unodes = solve_deps(resolved, unresolved)
    
    if len(unodes) == len(unresolved):
        # The dependency hasn't finished, continue solving it
        return solve_circular_deps(rnodes, unodes, nodes)
    else:
        resolved, unresolved = solve_deps(rnodes, unodes)
        while len(unresolved) != len(unodes):
            if len(unresolved) > len(unodes):
                resolved, unresolved = solve_deps(rnodes, unodes)
            else:
                rnodes, unodes = solve_deps(resolved, unresolved)
        
        # There were resolved nodes, return them
        return rnodes, unodes

        
def resolve_iter(resolved, unresolved, nodes):
    rnodes, unodes = solve_deps(resolved, unresolved)
    
    if len(unodes) == len(unresolved):
        # Nothing happened, I need to move to a new state
        # where I pick a single node and mark it as solved
        circular, unodes = solve_circular_deps([], unodes, nodes)
        rnodes.append(circular)
    
    return rnodes, unodes

def resolve_deps(items):
    """
    Returns an iterator with a sorted version of the dependencies that are provided
    through a list of pairs ('name', ['deps']).

    For example:

    >>> list(resolve_deps((
    ...    ('a', ('b', 'c', 'd')),
    ...    ('b', ('c', 'd')),
    ...    ('c', ('d',)),
    ...    ('d', ()),
    ... )))
    [('d', ()), ('c', ('d',)), ('b', ('c', 'd')), ('a', ('b', 'c', 'd'))]
    
    """
    unresolved = []
    nodes = {}
    
    for name, deps in items:
        nodes[name] = _DependencyNode(name, deps)
    
    for node in nodes.values():
        for dep in node.depends:
            if dep not in nodes:
                raise InsatisfiedDependencyError(dep)
    
    rnodes, unodes = resolve_iter([], nodes.values(), nodes)
    while len(unodes) > 0:
        rnodes, unodes = resolve_iter(rnodes, unodes, nodes)
    return rnodes

class _DependencyNode:
    name = None
    depends = None

    def __init__(self, name, depends):
        self.name = name
        self.depends = Set(depends)
        
        if name in self.depends:
            self.depends.remove(name)

    def __repr__(self):
        return "_DependencyNode(%r, %r)" % (self.name, self.depends)
    
    def has_deps(self):
        return len(self.depends) == 0
    
    def unlink_from_nodes(self, nodes):
        """
        Unliks this node from every node that depends on it
        """

        unlinked = False
        for node in nodes:
            if self.name in node.depends:
                node.depends.remove(self.name)
                unlinked = True
        return unlinked




##########################
import unittest
class TestDependencies(unittest.TestCase):

    def test_nodes(self):
        nodes = ([("foo", [])])
        sorted = resolve_deps(nodes)
        self.assertEquals(["foo"], sorted)

    def test_two_nodes(self):
        nodes = [("foo", ["bar"]), ("bar", ["g"]), ("g", [])]
        sorted = list(resolve_deps(nodes))
        target = ['g', 'bar', 'foo']
        self.assertEquals(target, sorted)
    
    def test_reflexive(self):
        nodes = [("foo", ("foo",))]
        sorted = list(resolve_deps(nodes))
        
        self.assertEquals(sorted, ["foo"])

    def test_mutual_triangular(self):
        nodes = [
            ("a", ("b", "c")),
            ("b", ("c", "a")),
            ("c", ("a", "b")),
        ]
        sorted = resolve_deps(nodes)
        self.assertEquals(1, len(sorted), sorted)
        sorted = sorted.pop()

        assert "a" in sorted, sorted
        assert "b" in sorted, sorted
        assert "c" in sorted, sorted


    def test_triangular(self):
        nodes = [
            ("a", ("b",)),
            ("b", ("c",)),
            ("c", ("d",)),
            ("d", ("e",)),
            ("e", ("a",)),
        ]
        sorted = list(resolve_deps(nodes))
        
        self.assertEquals(1, len(sorted), sorted)
        sorted = sorted.pop()
        self.assertEquals(5, len(sorted), sorted)

        assert "a" in sorted, sorted
        assert "b" in sorted, sorted
        assert "c" in sorted, sorted
        assert "d" in sorted, sorted
        assert "e" in sorted, sorted



if __name__ == '__main__':
    unittest.main()
